package interview.issubstring;


public class IsSubstring {
	
	/**
	 * Complexity: O(nm)
	 * @param source
	 * @param substr
	 * @return
	 */
	public boolean naiveAlgorithm(char[] source, char[] substr) {
		for(int j = 0; j < source.length; j++) {
			boolean equals = true;
			for(int i = 0; i < substr.length; i++) {
				if(source[j + i] != substr[i]) {
					equals = false;
					break;
				}
			}
			if(equals)
				return true;
		}
		return false;
	}
	
	/**
	 * Complexity: O(n+m)
	 * @param source
	 * @param substr
	 * @return
	 */
	public boolean KMP(char[] source, char[] substr) {
		int[] table = new int[substr.length];
		buildTable(table, substr);
		int m = 0;
		int i = 0;
		
		while(m+i < source.length) {
			if(substr[i] == source[m+i]) {
				if(i == substr.length - 1)
					return true;
				i++;
			} else {
				m = m + i - table[i];
				if(table[i] > -1) {
					i = table[i];
				} else {
					i = 0;
				}
			}
		}
		return false;
	}

	private void buildTable(int[] table, char[] substr) {
		int pos, cnd;
		pos = 2; 
		cnd = 0;
		table[0] = -1;
		table[1] = 0;
		while(pos < substr.length) {
			// (first case: the substring continues)
			if(substr[pos - 1] == substr[cnd]) {
				cnd++;
				table[pos] = cnd;
				pos++;
			} else if (cnd > 0) {
				// (second case: it doesn't, but we can fall back)
				cnd = table[cnd];
			} else {
				// (third case: we have run out of candidates.  Note cnd = 0)
				table[pos] = 0;
				pos++;
			}
		}
	}
}
